#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#define eq(A, B) (A == B)

typedef int Item;
typedef struct node* link;


struct node {
    Item item;
    link next;
};

int count(link x);

void tranverse(link h, void (*visit)(link));

void tranverseR(link h, void (*visit)(link));

link delete(link x, Item v);

void visit(link x);


//--------------------------------------------------
link create_list(Item items[], int n);
void free_list(link h);



/**
 * Program 5.5 Examples of recursive functions for linked lists
 * -----------------------------------------------------------------------------
 * These recursive functions for simple list-processing tasks are easy to express, 
 * but may not be useful for huge lists because the depth of the recursion may be proportional to the length of the list.
 * 
 * The first function, count, counts the number of nodes on the list.
 * The second, traverse, calls the function visit for each node on the list, from beginning to end.
 * These two functions are both also easy to implement with a for or while loop.
 * The third function, traverseR, does not have a simple iterative counterpart.
 * It calls the function visit for every node on the list, but in reverse order.
 * The fourth function, delete, makes the structural changes needed for a given item to be deleted from a list.
 * It returns a link to the (possibly altered) remainder of the list—the link returned is x,
 * except when x->item is v, when the link returned is x->next (and the recursion stops).
 */
int main(int argc, char** argv){
    printf("Testing count function\n");

    Item items1[] = {10, 20, 30};
    link list1 = create_list(items1, 3);
    Item items2[] = {5};
    link list2 = create_list(items2, 1);
    link list_empty = NULL;

    assert(count(list_empty) == 0);
    printf("count(empty) test passed.\n");

    assert(count(list2) == 1);
    printf("count(single_node) test passed.\n");

    assert(count(list1) == 3);
    printf("count(multi_node) test passed.\n");

    free_list(list_empty);
    free_list(list1);
    free_list(list2);


    Item items4[] = {10, 20, 30};
    link list4 = create_list(items4, 3);
    tranverse(list4, visit);
    tranverseR(list4, visit);
    free_list(list4);


    Item items5[] = {10, 20, 30};
    link list5 = create_list(items5, 3);
    list5 = delete(list5, 10);
    assert(count(list5) == 2);
    assert(list5->item == 20);
    list5 = delete(list5, 20);
    assert(count(list5) == 1);
    assert(list5->item == 30);
    list5 = delete(list5, 30);
    assert(count(list5) == 0);
    assert(list5 == NULL);
    free_list(list5);

    Item items6[] = {10, 20, 30};
    link list6 = create_list(items6, 3);
    list6 = delete(list6, 20);
    assert(count(list6) == 2);
    assert(list6->item == 10);
    list6 = delete(list6, 30);
    assert(count(list6) == 1);
    assert(list6->item == 10);
    list6 = delete(list6, 10);
    assert(count(list6) == 0);
    assert(list6 == NULL);
    free_list(list6);

    return 0;
}

int count(link x){
    if (x == NULL) {
        return 0;
    }
    return 1 + count(x->next);
}

void visit(link x){
    printf("%d\n", x->item);
}

void tranverse(link h, void (*visit)(link)){
    if (h == NULL) {
        return ;
    }
    (*visit)(h);
    tranverse(h->next, visit);
}

void tranverseR(link h, void (*visit)(link)){
    if (h == NULL) {
        return ;
    }
    tranverseR(h->next, visit);
    (*visit)(h);
}


link delete(link x, Item v){
    if (x == NULL) {
        return NULL;
    }
    if (eq(x->item, v)) {
        link t = x->next;
        free(x);
        return t;
    }
    x->next = delete(x->next, v);
    return x;
}


/**********************************************/
link create_list(Item items[], int n){
    link head = NULL;
    link tail = NULL;
    int i;
    for (i = 0; i < n; i++) {
        link t = malloc(sizeof(struct node));
        if (t == NULL) {
            printf("Failed to allocate node\n");
            exit(1);
        }
        t->item = items[i];
        t->next = NULL;
        if (head == NULL) {
            head = t;
            tail = t;
        }else {
            tail->next = t;
            tail = t;
        }
    }
    return head;
}

void free_list(link h){
    link next = NULL;
    link current = h;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
}

/*********************************************************/

